/*
 * @lc app=leetcode.cn id=241 lang=cpp
 *
 * [241] 为运算表达式设计优先级
 */

// @lc code=start
class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ans;
        int n = expression.size();
        for (int i = 0; i < n; i++) {
            char op = expression[i];
            if (op != '+' && op != '-' && op != '*') {
                continue;
            }

            vector<int> left = diffWaysToCompute(expression.substr(0, i));
            vector<int> right = diffWaysToCompute(expression.substr(i + 1));

            for (auto l : left) {
                for (auto r : right) {
                    switch (op) {
                    case '+':
                        ans.push_back(l + r);
                        break;
                    case '-':
                        ans.push_back(l - r);
                        break;
                    case '*':
                        ans.push_back(l * r);
                        break;
                    }
                }
            }
        }

        if (ans.size() == 0) {
            ans.push_back(stoi(expression));
        }

        return ans;
    }
};
// @lc code=end
